package 力扣_滑动窗口;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * @author zx
 * @create 2022-05-08 20:50
 */
public class 无重复字符的最长子串_3 {
    /**
     * 完美解释这个：left = Math.max(left,map.get(s.charAt(right)) + 1);
     1.首先,判断当前字符是否包含在map中,如果不包含,将该字符添加到map(字符,字符在数组下标)
     此时没有出现重复的字符,左指针不需要变化.此时不重复子串的长度为：i-left+1,与原来的maxLen比较,取最大值
     2.如果当前字符 ch 包含在 map中,此时有2类情况：
     1) 当前字符包含在当前有效的子段中,如：abca，当遍历到第二个a,当前有效最长子段是 abc,又遍历到a
     那么此时更新 left 为 map.get(a)+1=1,当前有效子段更新为 bca；
     2) 当前字符不包含在当前最长有效子段中,如：abba,我们先添加a,b进map,此时left=0,我们再添加b,发现map中包含b
     而且b包含在最长有效子段中,就是1)的情况,我们更新 left=map.get(b)+1=2,此时子段更新为 b,而且map中仍然包含a,map.get(a)=0
     随后,遍历到a,发现a包含在map中,且map.get(a)=0,如果像1)一样处理,就会发现left = map.get(a) + 1 = 1,实际上,left此时
     应该不变,left始终为2,子段变成 ba才对.

     为了处理以上2类情况,每次更新left, left=Math.max(left, map.get(ch) + 1).
     另外,更新left后,不管原来的 s.charAt(i) 是否在最长子段中,都要将 s.charAt(i) 的位置更新为当前的i
     因此此时新的s.charAt(i)已经进入到当前最长的子段中！
     */
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int res = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {
            // 出现重复的字符时：
            // 更新窗口的起始位置,要根据该命中的字符上一次出现的索引与当前窗口起始位置做比较,取最大值
            if (map.containsKey(s.charAt(right))) {
                left = Math.max(left, map.get(s.charAt(right)) + 1);
            }
            map.put(s.charAt(right), right);
            // 更新最大子串长度：用已攒的最大值与当前窗口大小作比较,取最大值
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    /**
     * @return 这道题看似要使用set,但是用set就复杂了,参考官方的set版本
     * 这是我自己写的set,是错的,很多测试用例过不了
     */
    public int lengthOfLongestSubstring2(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0;
        int res = 0;
        for(int right = 0;right < s.length();right++){
            if(!set.contains(s.charAt(right))){
                set.add(s.charAt(right));
            }else{
                set.remove(s.charAt(left));
                left++;
            }
            res = Math.max(res,right - left);
        }
        return res;
    }
}
